package com.peng.leetcode.search;

/**
 * BinnarySearch
 *
 * @author: lupeng6
 * @create: 2020/12/24 10:46
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] array = {4, 5, 6, 1, 2, 3};
//        int x = binarySearch2(array, 8);
//        int x = binarySearch3(array, 8);
//        int x = binarySearch4(array, 4);
//        int x = binarySearch5(array, 4);
        int x = binarySearch6(array, 2);
        System.out.println(x);
    }

    /**
     * 二分查找 1
     *
     * @author lupeng6
     * @date 2020/12/24 10:54
     */
    public static int binarySearch1(int[] array, int value) {
        int low = 0;
        int high = array.length - 1;
        while (low <= high) {
            int middle = low + (high - low) / 2;
            if (array[middle] == value) {
                return middle;
            } else if (array[middle] < value) {
                low = middle + 1;
            } else {
                high = middle - 1;
            }
        }
        return -1;
    }

    /**
     * 查找数组中第一个值等于给定值的元素
     *
     * @author lupeng6
     * @date 2020/12/24 10:55
     */
    public static int binarySearch2(int[] array, int value) {
        int low = 0;
        int high = array.length - 1;
        while (low <= high) {
            int middle = low + (high - low) / 2;
            if (array[middle] < value) {
                low = middle + 1;
            } else if (array[middle] > value) {
                high = middle - 1;
            } else {
                if (middle == 0 || array[middle - 1] != value) {
                    return middle;
                } else {
                    high = middle - 1;
                }
            }
        }
        return -1;
    }

    /**
     * 查找数组中最后一个值等于给定值的元素
     *
     * @author lupeng6
     * @date 2020/12/24 10:55
     */
    public static int binarySearch3(int[] array, int value) {
        int low = 0;
        int high = array.length - 1;
        while (low <= high) {
            int middle = low + (high - low) / 2;
            if (array[middle] < value) {
                low = middle + 1;
            } else if (array[middle] > value) {
                high = middle - 1;
            } else {
                if ((middle == array.length - 1) || array[middle + 1] != value) {
                    return middle;
                } else {
                    low = middle + 1;
                }
            }
        }
        return -1;
    }

    /**
     * 查找数组中 第一个值 大于等于给定值的元素
     *
     * @author lupeng6
     * @date 2020/12/24 10:55
     */
    public static int binarySearch4(int[] array, int value) {
        int low = 0;
        int high = array.length - 1;
        while (low <= high) {
            int middle = low + (high - low) / 2;
            if (array[middle] >= value) {
                if (middle == 0 || array[middle - 1] < value) {
                    return middle;
                } else {
                    high = middle - 1;
                }
            } else {
                low = middle + 1;
            }
        }
        return -1;
    }

    /**
     * 查找数组中 最后一个值 小于等于给定值的元素
     *
     * @author lupeng6
     * @date 2020/12/24 10:55
     */
    public static int binarySearch5(int[] array, int value) {
        int low = 0;
        int high = array.length - 1;
        while (low <= high) {
            int middle = low + (high - low) / 2;
            if (array[middle] <= value) {
                if (middle == array.length - 1 || array[middle + 1] > value) {
                    return middle;
                } else {
                    low = middle + 1;
                }
            } else {
                high = middle - 1;
            }
        }
        return -1;
    }

    /**
     * 在循环有序数组中查找对应的值
     *
     * @author lupeng6
     * @date 2020/12/24 11:30
     */
    public static int binarySearch6(int[] array, int value) {
        int low = 0;
        int high = array.length - 1;
        while (low <= high) {
            int middle = low + (high - low) / 2;
            if (array[middle] == value) {
                return middle;
            }

            // 判断 middle 在玄幻有序数组的的哪个位置
            if (array[0] <= array[middle]) {
                // 前半部分
                if (array[0] <= value && value < array[middle]) {
                    high = middle - 1;
                } else {
                    low = middle + 1;
                }
            } else {
                // 后半部分
                if (array[middle] < value && value <= array[array.length - 1]) {
                    low = middle + 1;
                } else {
                    high = middle - 1;
                }
            }
        }
        return -1;
    }

}
